Dimension dependent convex optimization

Consider a Convex function $f(\mathbf{x})$ bounded between $[-B,B]$ on a constraint set $\mathcal{S}$.

The Center-of-Gravity Method finds $\hat{\mathbf{x}}$ satisfying $f(\hat{\mathbf{x}}) ≤ \min_{\mathbf{x} \in \mathcal{S}} f(\mathbf{x}) + \epsilon$ using $O(d \log(B/\epsilon))$ calls to a function and gradient oracle for convex $f$.

#incomplete

see: Convex optimization

References:

1. https://cims.nyu.edu/~cfgranda/pages/OBDA_fall17/notes/convex_optimization.pdf